From bf5c5403575c9f84308d0bfda9549ef0903a5bad Mon Sep 17 00:00:00 2001
From: Benjamin Otte <otte@redhat.com>
Date: Tue, 21 Jul 2020 04:50:05 +0200
Subject: [PATCH] sortlistmodel: Properly compute runs

When updating a (partially) sorted model, take the known runs for the
existing sort and apply them to the new sort. That way, we don't have to
check the whole model again.

Benchmarks:

      appending half the items to a model of strings
                        old      new
      512,000 items   437ms    389ms
    1,024,000 items  1006ms    914ms

      appending 10% of the items to a model of strings
                        old      new
      512,000 items   206ms    132ms
    1,024,000 items   438ms    301ms

      appending 1 item to a model of strings
                        old      new
       64,000 items   1.8ms   0.00ms
      512,000 items     ---   0.01ms
---
 gtk/gtksortlistmodel.c | 55 ++++++++++++++++++++++++++++++------------
 1 file changed, 39 insertions(+), 16 deletions(-)

diff --git a/gtk/gtksortlistmodel.c b/gtk/gtksortlistmodel.c
index 5fa3105323..49fa234e14 100644
--- a/gtk/gtksortlistmodel.c
+++ b/gtk/gtksortlistmodel.c
@@ -414,6 +414,7 @@ gtk_sort_list_model_update_items (GtkSortListModel *self,
                                   guint            *unmodified_end)
 {
   guint i, n_items, valid;
+  guint run_index, valid_run, valid_run_end, run_end;
   guint start, end;
   gpointer *old_keys;
 
@@ -445,28 +446,50 @@ gtk_sort_list_model_update_items (GtkSortListModel *self,
 
   /* then, update the positions */
   valid = 0;
-  for (i = 0; i < n_items; i++)
+  valid_run = 0;
+  valid_run_end = 0;
+  run_index = 0;
+  run_end = 0;
+  for (i = 0; i < n_items;)
     {
-      guint pos = ((char *) self->positions[i] - (char *) old_keys) / self->key_size;
-
-      if (pos >= position + removed)
-        pos = pos - removed + added;
-      else if (pos >= position)
-        { 
-          start = MIN (start, valid);
-          end = n_items - i - 1;
-          continue;
+      if (runs[run_index] == 0)
+        {
+          run_end = n_items;
+          valid_run_end = G_MAXUINT;
+        }
+      else
+        {
+          run_end += runs[run_index++];
         }
 
-      self->positions[valid] = key_from_pos (self, pos);
-      valid++;
-    }
-  self->positions = g_renew (gpointer, self->positions, n_items - removed + added);
+      for (; i < run_end; i++)
+        {
+          guint pos = ((char *) self->positions[i] - (char *) old_keys) / self->key_size;
+
+          if (pos >= position + removed)
+            pos = pos - removed + added;
+          else if (pos >= position)
+            { 
+              start = MIN (start, valid);
+              end = n_items - i - 1;
+              continue;
+            }
 
-  /* FIXME */
-  runs[0] = 0;
+          self->positions[valid] = key_from_pos (self, pos);
+          valid++;
+        }
 
+      if (valid_run_end < valid)
+        {
+          runs[valid_run++] = valid - valid_run_end;
+          valid_run_end = valid;
+        }
+    }
+  g_assert (i == n_items);
   g_assert (valid == n_items - removed);
+  runs[valid_run] = 0;
+
+  self->positions = g_renew (gpointer, self->positions, n_items - removed + added);
 
   self->n_items = n_items - removed + added;
 
-- 
2.30.2